\documentclass[12pt]{article}
\usepackage{amsmath}
\begin{document}
\title{Dr.John Burns}
\author {Umar Riaz - x00097977}
\date{\today}
\maketitle
Continous Assessment 1
\section{Question-1}
\begin{enumerate}
\item Derive the best, worst AND average case O estimates for this sorting function
\par
In this algorithm swap takes $O(1)$ time
\par
FillRandomData takes $O(1)$ time
\par
Outer loop will run $(n-i)$ times i.e SIZE times
\par
Inner loop wil execute $j=i--1  
i.e O (2n)$
\par
so total number of times the loops will be executed will be
\par
\begin{equation}
\sum_{i=1}^{n-1} (n-1)(2n)=2n(n-1)\\
\nonumber
\end{equation}
\begin{equation}
2n(n-1)/2={n}^2/2-n/2
\nonumber
\end{equation}
\par
\begin{equation}
{n}^2= O( {n}) ^2
\nonumber
\end{equation}
\par
So, we can say that $ f (x) \in O ( {n} ) ^2$
\par
Big Oh Notation is upper limeit to the growth of a function as input gets larger where
$ f(x) $ is the problem and n is the input that measures the size of x.
\begin{enumerate}
\item The Best case O estimates for this funcion
\par
In the best case Big Oh remains ${n}^2$ as there is no mechanism to break the inner loop at the first test if we already find the elements in the sorted order. Also there is no mechanism that we can stop the inner loop not to go through all those elelments that has already been sorted.
\item The Worst case O estimates for this funcion
\par In the worst case
\begin{equation}
E (i=1) \rightarrow n \, and \, E (j=i) \rightarrow 1 
\nonumber
\end{equation}
\begin{equation}
 (n-i)={n}^2-(n+1)/2 = {n}^2/2-n/2
\nonumber
\end{equation}
$ = O ({n}^2) $
\item The Average case O estimates for this funcion.
\par For the average case O estimates for this function is the same Big Oh Notation i.e $O ( {n}^2 $ 
\par
as if we'l take many random samples and divide it by the number of sample the average case will remain the same as
$ O ( {n}^2 ) $
\par
$
{n}^2+{n}^2+{n}^2.....+{n}^2/number of samples
$

\end{enumerate}
\item  Is this algorithm sensitive to input data permutation (or ordering)?
\par
Yes this algorithm is sensitive to the data permutation i.e is input data size as input data size increases time to sort becomes double as this algorithm is $O({n}^2)$. Also we can say that it is sensitive to that size of data because here in this algorithm $ f (x) \in O ( {n} ) ^2$.Its not sensitive to the ordering as as even the half of the array/input or even the full array is in sorted order still it will go through all the items one by one to try to sort them in order.
\item   Discuss how this algorithm compares to the sorting methodology of
the Selection sort we saw in the lecture notes. Give an example.
\par
In the seclection sort we have to swap an item once but in the bubble sort a single item will be or may be swapped many times before reaching its final destination i.e place. For example following is an unsorted array of integers when we will run it through our algortihm implementation it will give the follwoing result at each pass through out/inner loop.
\\
\\
\\Unsorted data during Bubble Sort.\\
\begin{tabular}{|c|c|c|c|c|cl}
\par
\hline
11 & 61 & 45 & 25 & 15 \\
\hline
\end{tabular}
\par
After the first pass this will become \\
\begin{tabular}{|c|c|c|c|c|cl}
\par
\hline
11 & 45 & 61 & 25 & 15 \\
\hline
\end{tabular}
\par
After the 2nd pass this will become\\
\begin{tabular}{|c|c|c|c|c|cl}
\hline
11 & 45 & 61 & 25 & 15 \\
\hline
\end{tabular}
\par
After the 3rd pass this will become\\
\begin{tabular}{|c|c|c|c|c|cl}
\hline
11 & 45 & 61 & 25 & 15 \\
\hline
\end{tabular}
\par
After the 4th pass this will become\\
\begin{tabular}{|c|c|c|c|c|cl}
\hline
11 & 45 & 61 & 25 & 15 \\
\hline
\end{tabular}
\par
After the 5th pass this will become\\
\begin{tabular}{|c|c|c|c|c|cl}
\hline
11 & 45 & 25 & 61 & 15 \\
\hline
\end{tabular}
\par
After the 6th pass this will become\\
\begin{tabular}{|c|c|c|c|c|cl}
\hline
11 & 25 & 45 & 61 & 15 \\
\hline
\end{tabular}
\par
After the 7th pass this will become\\
\begin{tabular}{|c|c|c|c|c|cl}
\hline
11 & 25 & 15 & 45 & 61 \\
\hline
\end{tabular}
\par
After the 8nd pass this will become\\
\begin{tabular}{|c|c|c|c|c|cl}
\hline
11 & 15 & 25 & 45 & 61 \\
\hline
\end{tabular} 
\\
\par
While in selection sort the same above result will be concluded but with one difference i.e it will first of all look for the smallest item in the array and will bring it to the very first place and then the Pointer for sorting will b moved to the next item in the array and similarly next smallest item will be brought to the 2nd place in the array without checking the first element. Then Seleciton Sort will go for the third element leaving the first two elements. Selection Sort will not go through again and again the sorted element unlike bubble sort. So we can say that on each pass data size is being decreased to work on it.
\end{enumerate}
\section{Question-2}
\label{Alogorithm Implementation}
\par
Please check the attached file 
\par

\end{document}
